package com.ddd.demo.test;

public class MyHeap {

    private int[] data;
    private int size;

    public MyHeap(int length) {
        this.data = new int[length];
        this.size = 0;
    }

    void swap(int i, int j){
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    int getParent(int i){
        return (i - 1) / 2;
    }

    void insert(int value){
        data[size++] = value;
        shiftUp(size - 1);
    }

    private void shiftUp(int index) {
        while (index > 0 && data[index] < data[getParent(index)]){
            swap(index,getParent(index));
            index = getParent(index);
        }
    }

    int peek(){
        return data[0];
    }


    public static void main(String[] args) {
        MyHeap myHeap = new MyHeap(10);
        myHeap.insert(5);
        myHeap.insert(3);
        myHeap.insert(7);
        myHeap.insert(1);

        System.out.println(myHeap.peek());

        int value = myHeap.remove();
        System.out.println("value = " + value);
    }

    private int remove() {
        int tmp = data[0];
        data[0] = data[size-1];
        size--;
        shiftDown(0);
        return tmp;
    }

    private void shiftDown(int index) {
        int minIndex = index;
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        while (left < size && data[left] < data[minIndex]){
            minIndex = left;
        }
        while (right < size && data[right] < data[minIndex]){
            minIndex = right;
        }
        if(minIndex != index){
            swap(minIndex,index);
            shiftDown(minIndex);
        }
    }
}
